P2598 [ZJOI2009]狼和羊的故事

发表于

闲扯

今天上课将网络流例题，难得的想出怎么建图的几个题之一。。

题面

题面

Solution

因为只有羊和狼两种生物，且不能分到同一个集合中，所以可以建立二分图。而我们要用最少的篱笆，将狼和羊分开，考虑最小割。

虚拟一个超级源点，连向所有是狼的格子，流量为 $INF$ ，表示这个边不能割。

虚拟一个超级汇点，将所有是羊的格子连向它，流量为 $INF$ ，理由同上。

然后对于每一个格子，向他的四周连一条流量为 $1$ 的边，表示在这两个格子之间修一个篱笆，费用为 $1$ 。

当然，如果相邻两个格子都是狼或者都是羊，就不用连了，因为没必要在这里修篱笆。

然后跑最小割，每条割边表示在这里修一个篱笆。

正确性：对于所有的狼、羊，都是连着源点、汇点的，流量为 $INF$ ，一定不会割这些边，而狼和羊、空格子连边代表篱笆，这个图的最小割集使得该图分为只含狼、只含羊的两个集合，也就满足了题意。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il print(T x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(res*bas)%mod;
		bas=(bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 105;
int n,m,s,t,val[MAXN][MAXN],cur[MAXN*MAXN],head[MAXN*MAXN],num_edge=-1,dis[MAXN*MAXN];
struct Edge{
	int next,to,w;
	Edge(){}
	Edge(int next,int to,int w):next(next),to(to),w(w){}
}edge[MAXN*MAXN*9];
il add_edge(int u,int v,int w){
	edge[++num_edge]=Edge(head[u],v,w),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u,0),head[v]=num_edge;
}
inl bool BFS(int s,int t){
	del(dis,0),dis[s]=1;
	queue<int> q;q.push(s);
	while(!q.empty()){
		ri pos=q.front();q.pop();
		for(ri i=head[pos];i!=-1;i=edge[i].next)
			if(!dis[edge[i].to]&&edge[i].w>0){
				dis[edge[i].to]=dis[pos]+1;
				if(edge[i].to==t) return true;
				q.push(edge[i].to);
			}
	}
	return false;
}
it DFS(int now,int t,int flow){
	if(now==t) return flow;
	ri s=0,k;
	for(ri &i=cur[now];i!=-1;i=edge[i].next)
		if(dis[edge[i].to]==dis[now]+1&&edge[i].w>0){
			k=DFS(edge[i].to,t,min(flow-s,edge[i].w));
			s+=k,edge[i].w-=k,edge[i^1].w+=k;
			if(s==flow) break;
		}
	if(s==0) dis[now]=0;
	return s;
}
it Dinic(int s,int t){
	ri res=0;
	while(BFS(s,t)){
		memcpy(cur,head,sizeof(head));
		res+=DFS(s,t,INF);
	}
	return res;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),del(head,-1),t=n*m+1;
	for(ri i=1;i<=n;++i)
		for(ri j=1;j<=m;++j)
			read(val[i][j]);
	for(ri i=1;i<=n;++i)
		for(ri j=1;j<=m;++j){
			if(val[i][j]==1) add_edge(s,(i-1)*m+j,INF);
			if(val[i][j]==2) add_edge((i-1)*m+j,t,INF);
			if(i!=1&&(val[i][j]!=val[i-1][j]||!val[i][j])) add_edge((i-1)*m+j,(i-2)*m+j,1);
			if(i!=n&&(val[i][j]!=val[i+1][j]||!val[i][j])) add_edge((i-1)*m+j,i*m+j,1);
			if(j!=1&&(val[i][j]!=val[i][j-1]||!val[i][j])) add_edge((i-1)*m+j,(i-1)*m+j-1,1);
			if(j!=m&&(val[i][j]!=val[i][j+1]||!val[i][j])) add_edge((i-1)*m+j,(i-1)*m+j+1,1);
		}
	printf("%d",Dinic(s,t));
	return 0;
}

总结

这应该是一个比较简单的最小割的题吧，建图比较明显，看到两种不同的东西，不能分在一起，可以往这方面联想一下。